package com.qfedu.entity.course08;

public class RBTree {
    RBTreeNode root; //根节点

    public static void main(String[] args) {
        RBTree rb = new RBTree();
        rb.insertValue(10);//根节点
        rb.insertValue(5);
        rb.insertValue(9);
        rb.insertValue(3);
        rb.insertValue(6);
        rb.insertValue(7);
        rb.insertValue(19);
        rb.insertValue(32);
        rb.insertValue(24);
        rb.insertValue(17);
    }

    public RBTreeNode find(int value) {
        RBTreeNode node = root;
        //根据二叉搜索树的特点进行  查找
        while (node != null) {
            if (value == node.value) {//找到节点，返回
                return node;
            } else if (value < node.value) {//在左侧继续查找
                node = node.left;
            } else {//在右侧继续查找
                node = node.right;
            }
        }
        return null;
    }

    /*
     * 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，
     * 右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变
     *
     *   node               right
     *  /    \    左旋转     /   \
     *left right -------> node  rr
     *      / \           /  \
     *     rl rr        left rl
     *
     */
    private void leftRotate(RBTreeNode node) {
        //父节点
        RBTreeNode parent = node.parent;
        //右节点
        RBTreeNode right = node.right;
        if (parent == null) {//父节点为空，right成为根节点
            root = right;
            right.parent = null;
        } else {
            //设置父节点和right成为父子关系
            if (parent.left == node) {
                parent.left = right;
            } else {
                parent.right = right;
            }
            right.parent = parent;
        }
        //right为node的父节点
        node.parent = right;
        //right的左子树成为node的右子树
        node.right = right.left;
        if (right.left != null) {
            right.left.parent = node;//设置父节点
        }
        //node 为 right 的左子节点
        right.left = node;
    }

    /*
     * 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，
     * 左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变
     *
     *    node               left
     *   /    \     右旋     /   \
     * left right -------> ll   node
     * / \                      /  \
     *ll lr                   lr right
     *
     */
    private void rightRotate(RBTreeNode node) {
        RBTreeNode parent = node.parent;//父节点
        RBTreeNode left = node.left;//左节点
        if (parent == null) {//父节点为空，left 成为根节点
            root = left;
            left.parent = null;
        } else {//设置父节点和 left 成为父子关系
            if (parent.left == node) parent.left = left;
            else parent.right = left;
            left.parent = parent;
        }
        node.parent = left;//left 为node的父节点
        node.left = left.right;//left 的右子树成为node的左子树
        if (left.right != null)
            left.right.parent = node;//设置父节点
        left.right = node; // node 为 left 的右子节点
    }

    public void insertValue(int value) {
        RBTreeNode node = new RBTreeNode(value);

        //情况1：空树，新插入节点为根节点，设置为黑色
        if (root == null) {
            node.isRed = false;//根是黑色的
            root = node;
            return;
        }

        //新插入节点不是根节点，则需要查找待插入位置
        RBTreeNode position = root;
        RBTreeNode parent = null;
        boolean isLeftChild = false;
        while (position != null) {
            parent = position;
            if (value < parent.value) {
                position = parent.left;
                isLeftChild = true;
            } else if ((value > parent.value)) {
                position = parent.right;
                isLeftChild = false;
            } else {
                //节点已经存在，更新节点对象的值，这里是整型数字，直接返回
                return;
            }
        }

        //将新节点插入到对应父节点的下面
        if (isLeftChild) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.parent = parent;

        // 情况2：插入位置的父节点为黑色，新节点默认红色，直接插入 无需调整平衡
        if (parent.isBlack()) {
            return;
        }

        // 父节点为红色，插入后两个红色相邻，违反规则，需要进行自平衡 调整
        balanceInsert(node);
    }

    private void balanceInsert(RBTreeNode node) {
        RBTreeNode parent, grandParent;
        //父节点为红色
        while ((parent = node.parent) != null && parent.isRed) {
            grandParent = parent.parent; //爷爷节点
            //获得叔伯节点
            RBTreeNode uncle = grandParent.left;
            if (uncle == parent) {
                uncle = grandParent.right;
            }
            //情况3：父节点为红色，叔伯节点也为红色 父节点、叔伯节点都转为黑色、爷爷转为红色
            if (uncle != null && uncle.isRed) {
                parent.isRed = false;
                uncle.isRed = false;
                grandParent.isRed = true;
                node = grandParent;
                // 后续还要继续验证爷爷变为红色是否破坏平衡性，判断爷爷的父节点颜色
                continue;
            }

            //父节点为红色，叔伯节点为黑色（包含叔伯不存在）
            if (grandParent.left == parent) {// 父节点 为 爷爷节点的 左孩子

                //情况4：父节点为红色，叔伯节点为黑色（包含叔伯不存在）， 爷爷 父亲 新节点形成 ㄑ 字型，先进行左旋转成情况5
                if (node == parent.right) {
                    //以父节点为中心进行左旋
                    leftRotate(parent);
                    //node 与 parent 交换
                    RBTreeNode tmp = node;
                    node = parent;
                    parent = tmp;
                }

                //情况5： 父节点为红色，叔伯节点为黑色（包含叔伯不存在），爷爷 父亲 新节点形成 左侧一条线 /  父变黑、爷变红再以爷爷为中心右旋
                parent.isRed = false;
                grandParent.isRed = true;
                rightRotate(grandParent);//右旋
            } else {//父节点 为 爷爷节点的 右孩子

                //情况6：父节点为红色，叔伯节点为黑色（包含叔伯不存在）， 爷爷 父亲 新节点形成 〉型，右旋转成情况7
                if (node == parent.left) {
                    //以父节点为中心进行右旋
                    rightRotate(parent);
                    //node 与 parent 交换
                    RBTreeNode tmp = node;
                    node = parent;
                    parent = tmp;
                }

                //情况7：父节点为红色，叔伯节点为黑色（包含叔伯不存在），爷爷 父亲 新节点形成 右侧一条线 \ 父变黑、爷变红再以爷爷为中心右旋
                parent.isRed = false;
                grandParent.isRed = true;
                leftRotate(grandParent);//左旋
            }
        }

        //保证根节点为黑色
        root.isRed = false;
    }

    /**
     * From CLR 来源于算法导论
     * 本分支删除了一个黑色节点，需要向上传递将父辈第一个红节点变成黑色
     * （同时不能影响兄弟分支的深度，需要通过变色、左右旋保证兄弟分支和本分支拉起深度)
     */
    private void balanceDeletion(RBTreeNode node) {
        while (node != root && node != null && node.isBlack()) { //为黑色节点，删除会使得深度-1,需增加一个黑节点，同时不能改变兄弟分支深度
            if (node.parent != null && node == node.parent.left) {//节点为父节点的左孩子
                RBTreeNode brother = node.parent.right;//除根节点外黑色节点一定存在兄弟节点
                //细分情况1：为黑在左兄为红，父兄变色父左旋
                if (brother != null && brother.isRed) {//兄弟节点为红色
                    //兄弟节点变为黑色，爷爷节点变为红色,然后以父节点为中心左旋
                    brother.isRed = false;
                    node.parent.isRed = true;
                    leftRotate(node.parent); // 兄弟节点变为父节点
                    brother = node.parent.right;//获取新的兄弟节点
                }

                //细分情况2：为黑在左兄为黑，侄子都为黑，兄变红向上验
                if ((brother.left == null || brother.left.isBlack()) &&
                        (brother.right == null || brother.right.isBlack())) { //兄弟节点的左右孩子都为黑色（含叶子节点情况）
                    brother.isRed = true;//兄弟节点置为红色
                    node = node.parent;//兄弟之间深度已经拉起了，继续向上找红色节点变成黑色就可以了
                } else {//兄弟节点的孩子节点不都是黑色
                    //细分情况3：为黑在左兄为黑，左侄为红，兄侄变色兄右旋
                    if (brother.left != null && brother.left.isRed) { //兄弟节点左孩子为红色
                        brother.left.isRed = false;//兄弟节点的左孩子变为黑色
                        brother.isRed = true;//兄弟节点变为红色
                        rightRotate(brother);//以兄弟节点为中心右转
                        brother = node.parent.right;//获取新的兄弟节点
                    }
                    //细分情况4：为黑在左兄为黑，左侄不为红，父兄变色父左旋，退循环
                    brother.isRed = node.parent.isRed; //兄弟节点设为父节点颜色
                    node.parent.isRed = false;//父节点设为黑色
                    if (brother.right != null)
                        brother.right.isRed = false;

                    //左旋
                    leftRotate(node.parent);
                    //循环可以结束了
                    node = root;
                }
            } else { // symmetric  对称  //节点为父节点的右孩子
                //兄弟节点
                RBTreeNode brother = node.parent.left;

                //细分情况5：为黑在右兄为红，父兄变色父右旋
                if (brother != null && brother.isRed) {
                    brother.isRed = false;
                    node.parent.isRed = true;
                    rightRotate(node.parent);
                    brother = node.parent.left;// 此时兄弟节点就是黑色的了
                }

                //细分情况6：为黑在右兄为黑，侄子都为黑，兄变红向上验
                if ((brother.right == null || brother.right.isBlack()) &&
                        (brother.left == null || brother.left.isBlack())) {
                    brother.isRed = true;
                    node = node.parent;//兄弟之间深度已经拉起了，继续向上找红色节点变成黑色就可以了
                } else {
                    //细分情况7：为黑在右兄为黑，右侄为红，兄侄变色兄左旋
                    if (brother.left == null || brother.left.isBlack()) {//兄弟节点左孩子为黑色或不存在，变色、左旋
                        brother.right.isRed = false;
                        brother.isRed = true;
                        leftRotate(brother);
                        brother = node.parent.left;
                    }
                    //情况8：为黑在右兄为黑，右侄不为红，父兄变色父右旋，退循环
                    brother.isRed = node.parent.isRed;
                    node.parent.isRed = false;
                    if (brother.left != null)
                        brother.left.isRed = false;
                    //右旋
                    rightRotate(node.parent);
                    //循环可以结束了
                    node = root;
                }
            }
        }
        //节点设为黑色，还原深度
        if (node != null)
            node.isRed = false;
    }

    public void deleteValue(int value) {
        RBTreeNode node = find(value);
        //存在目标节点，则删除节点
        if (node != null) {
            deleteNode(node);
        }
    }


    private void deleteNode(RBTreeNode node) {
        //情况1：删除节点有两个子节点的话，先找到后继结点，后继节点的值给到删除节点，删除节点指向后继节点（后面视作对后继节点进行删除）
        if (node.left != null && node.right != null) {
            RBTreeNode s = findSuccessor(node); //找后继节点，后继结点没有左节点 或者 是父辈节点作为后继
            node.value = s.value;
            node = s;
        }

        //选择替代节点，优先选择左子节点补位，左子节点不存在则使用右字节点补位 node为待删除的节点
        RBTreeNode replacement = (node.left != null ? node.left : node.right);
        if (replacement != null) {//存在替代节点
            //情况2：将替代节点 提到当前删除节点的位置
            replacement.parent = node.parent;
            if (node.parent == null) //为根节点
                root = replacement;
            else if (node == node.parent.left) //node为其父节点的左节点
                node.parent.left = replacement;
            else //node为其父节点的右节点
                node.parent.right = replacement;

            // node的相关指针置空
            node.left = node.right = node.parent = null;

            //情况3：删除节点为黑色，会使得深度减少1，需要进行 自平衡 调整（在规则下将替代节点变为红色）
            if (node.isBlack())
                balanceDeletion(replacement); //此时树上已不存在node节点
            //否则删除节点为红节点，不破坏平衡
        } else if (node.parent == null) {//没有替代节点，同时删除节点没有父节点
            //删除的节点为唯一节点
            root = null;
        } else {
            //没有替代节点，也就是删除节点没有子节点的话
            if (node.isBlack()) //情况4：删除节点为黑色，会使得深度减少1，需要进行 自平衡 调整（在规则下将删除节点变为红色）
                balanceDeletion(node);

            //情况5：删除节点为红节点，不破坏平衡 删除对该节点的相关引用
            if (node.parent != null) {
                if (node == node.parent.left)
                    node.parent.left = null;
                else if (node == node.parent.right)
                    node.parent.right = null;
                node.parent = null;
            }
        }
    }

    public RBTreeNode findSuccessor(RBTreeNode node) {
        if (node == null)
            return null;
        else if (node.right != null) {//存在右节点
            RBTreeNode p = node.right;
            while (p.left != null)//找右节点的最左侧的底层 孙节点
                p = p.left;
            return p;
        } else {//不存在右节点，向上找作为后继节点的父节点, 直到自己所在分支是父节点的左节点
            RBTreeNode parent = node.parent;
            RBTreeNode current = node;
            while (parent != null && current == parent.right) {//向上找作为后继节点的父节点, 直到自己不是父节点的右子节点
                current = parent;
                parent = parent.parent;
            }
            return parent;
        }
    }
}